Paper 2021/808

SNARGs for $\mathcal{P}$ from LWE

Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin

Abstract

We provide the first construction of a succinct non-interactive argument (SNARG) for *all* polynomial time deterministic computations based on standard assumptions. For $T$ steps of computation, the size of the proof and the common random string (CRS) as well as the verification time are poly-logarithmic in $T$. The security of our scheme relies on the hardness of the Learning with Errors (LWE) problem against polynomial-time adversaries. Previously, SNARGs based on standard assumptions could support bounded-depth computations and required sub-exponential hardness assumptions [Jawale-Kalai-Khurana-Zhang, STOC'21]. Along the way, we also provide the first construction of non-interactive batch arguments for $\mathsf{NP}$ based solely on the LWE assumption.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. FOCS 2021
Keywords
SNARGsDelegation schemesBatch arguments
Contact author(s)
achoud @ cs jhu edu
abhishek @ cs jhu edu
zjin12 @ jhu edu
History
2021-11-08: revised
2021-06-16: received
See all versions
Short URL
https://ia.cr/2021/808
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/808,
      author = {Arka Rai Choudhuri and Abhishek Jain and Zhengzhong Jin},
      title = {{SNARGs} for $\mathcal{P}$ from {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/808},
      year = {2021},
      url = {https://eprint.iacr.org/2021/808}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.